class Solution {
 public:
  // 1. dp[i]表示爬到第i梯的方法数
  // 2.
  // dp[i]=dp[i-1]+dp[i-2]；可从状态转移方程看出3、4步以及是否可以进行空间优化
  // 3. dp[1]=1,dp[2]=2
  // 4. n:1->n
  // 5. 检查dp数组的值
  /*
  int climbStairs(int n) {
      if(n==1) return 1;
      else if(n==2) return 2;
      vector<int>dp(n+1);
      dp[1]=1;
      dp[2]=2;
      int i;
      for(i=3;i<=n;i++) {
          dp[i]=dp[i-1]+dp[i-2];
      }
      return dp[n];
  }
  */
  // 空间优化
  int climbStairs(int n) {
    if (n == 1)
      return 1;
    else if (n == 2)
      return 2;
    int a = 1, b = 2, c;
    int i;
    for (i = 3; i <= n; i++) {
      c = a + b;
      a = b;
      b = c;
    }
    return c;
  }
};
// 此题与L509斐波那契数列几乎完全相同，只不过这题不用考虑n==0的情况；
// TODO: 1...m梯，变化为多重背包问题